已知有序数列A[1..n]和一个正整数x，设计一个复杂度为O(n)的算法，判断A中是否有两个元素它们的和是x。

来源：百度知道 编辑：UC知道 时间：2024/06/24 12:40:28
数列中若是整数我会做，但若是分数该如何求解呢？
我的整数解法是用空间换时间，就是用x减去所有大于x/2的数，得出结果放在一个大小为[x/2]的数组a中，其值与数组中的位置对应，若有此值，则数组相应位置设为1，然后遍历小于x/2的数，对数m，若数组中对应位置a[m]为1，则返回true，若没有一个对应位置为1，则为false...

你的算法不够好，如果整数很大(比如都是10亿以上),你哪有那么大的内存去开数组呢?

有一个算法是:
建立两个指针p,q,p指向数组第一个元素，q指向数组最后一个元素,[p]表示p内容，算法可以写成:

while(p <= q)
{
if(2 * [q] < x)
break;
if(2 * [q] == x)
return true;
for(;p < q;p++)
{
if([p] + [q] == x)
return true;
if([p] + [q] > x)
break;
}
q--;
}
return false;

数组每个元素最多只被p,q一个指针扫描一次，所以总时间复杂度O(N),而且数组元素可以为任意类型